package com.linwen.excise.algorithm.贪心;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;


/**
 * leetcode 435
 * */
public class _07 {
    public static void main(String[] args) {
        // {{-52,31},{-73,-26},{82,97},{-65,-11},{-62,-49},{95,99},{58,95},{-31,49},{66,98},{-63,2},{30,47},{-40,-26}}
        // {{1,2},{2,3},{3,4},{1,3}}
        int[][] intervals = new int[][]{{1,2},{1,3},{2,3},{3,4}};
        System.out.println(eraseOverlapIntervals(intervals));
    }

    private static int eraseOverlapIntervals(int[][] intervals) {
        List<Line> lineArrayList = new ArrayList<>(intervals.length);
        for (int i = 0; i < intervals.length; i++) {
            Line line = new Line(intervals[i][0], intervals[i][1]);
            lineArrayList.add(line);
        }
        //
        lineArrayList.sort(Comparator.comparingInt(o -> o.end));
        for (Line l :lineArrayList){
            System.out.println(l);
        }
        int result = 0;
        int forIndex = 0;
        while (true){
            if(forIndex+1==lineArrayList.size()){
                break;
            }
            if(lineArrayList.get(forIndex).isDup(lineArrayList.get(forIndex+1))){
                lineArrayList.remove(forIndex+1);
                result++;
            }else{
                forIndex++;
            }

        }
        System.out.println("=====================");
        for (Line l :lineArrayList){
            System.out.println(l);
        }
        return result;
    }

    private static class Line{
        int start;
        int end;
        Line(int start,int end){
            this.start = start;
            this.end = end;
        }

        public  boolean isDup(Line o2){
            if(this.end<=o2.start){
                return false;
            }
            return true;
        }

        @Override
        public String toString() {
            return "Line{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }
}
